package com.chenxys.algorithm.leetcode;

import com.chenxys.algorithm.common.StringUtil;

import java.util.Stack;

/**
 * <p>
 *      <a href="https://leetcode.cn/problems/minimum-string-length-after-removing-substrings/description/">删除子串后的字符串最小长度</a><br/>
 *      给你一个仅由 大写 英文字符组成的字符串 s 。<br/>
 *      你可以对此字符串执行一些操作，在每一步操作中，你可以从 s 中删除 任一个 "AB" 或 "CD" 子字符串。<br/>
 *      通过执行操作，删除所有 "AB" 和 "CD" 子串，返回可获得的最终字符串的 最小 可能长度。<br/>
 *      注意，删除子串后，重新连接出的字符串可能会产生新的 "AB" 或 "CD" 子串。<br/>
 *      例: <br/>
 *          输入：s = "ABFCACDB"<br/>
 *          输出：2<br/>
 *          解释：你可以执行下述操作：<br/>
 *              - 从 "ABFCACDB" 中删除子串 "AB"，得到 s = "FCACDB" 。<br/>
 *              - 从 "FCACDB" 中删除子串 "CD"，得到 s = "FCAB" 。<br/>
 *              - 从 "FCAB" 中删除子串 "AB"，得到 s = "FC" 。<br/>
 *              最终字符串的长度为 2 。<br/>
 *              可以证明 2 是可获得的最小长度。<br/>
 * </p>
 *
 * @author Chenxys
 * @version V1.0
 * @Package com.chenxys.algorithm.leetcode
 * @date 2024/1/10 10:07
 * @Copyright ©
 */
public class LeetCode2696 {

    /**
     * <p>
     *     获取删除子串后的字符串最小长度,使用栈 如果相邻两元素为A B C D 则直接弹出栈
     * </p>
     * @param s 原字符串
     * @return 删除AB、CD后的最小长度
     */
    public static int minLength(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            stack.add(s.charAt(i));
            int stackSize = stack.size();
            if (stackSize >= 2 && ((stack.get(stackSize - 2) == 'A' && stack.get(stackSize - 1) == 'B') ||
                    (stack.get(stackSize - 2) == 'C' && stack.get(stackSize - 1) == 'D'))) {
                stack.remove(stackSize - 1);
                stack.remove(stackSize - 2);
            }
        }
        return stack.size();
    }

    /**
     * <p>
     *     获取删除子串后的字符串最小长度,使用数组 如果相邻两元素为A B C D 则数组下标自减,使后面覆盖
     * </p>
     * @param s 原字符串
     * @return 删除AB、CD后的最小长度
     */
    public static int minLengthByArr(String s) {
        char[] chars = new char[s.length()];
        int minLen = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 首元素直接加入数组
            if (minLen == 0) {
                chars[minLen] = c;
                minLen++;
                continue;
            }
            // 如果当前元素为B 且上一个元素为A  或者 当前元素为D 上一个元素为C
            if ((c == 'B' && chars[minLen - 1] == 'A')|| (c == 'D') && chars[minLen - 1] == 'C') {
                // 数组下标自减 并继续[为后面元素的覆盖提供索引]
                minLen--;
                continue;
            }
            // 如果都不是,继续赋值并自增
            chars[minLen] = c;
            minLen++;
        }
        return minLen;
    }

    /**
     * <p>
     *     使用暴力替换方式,直接将AB CD 替换为空字符串
     * </p>
     * @param s 原字符串
     * @return 删除AB、CD后的最小长度
     */
    public static int checkMinLength(String s) {
        while (s.contains("AB") || s.contains("CD")) {
            s = s.replace("AB", "").replace("CD", "");
        }
        return s.length();
    }

    public static void main(String[] args) {
        int maxLen = 100;
        int testTimes = 100000;
        System.out.println("Test Start!");
        for (int i = 0; i < testTimes; i++) {
            String randomUpperStr = StringUtil.generateRandomUpperStr(maxLen);
            if (minLength(randomUpperStr) != minLengthByArr(randomUpperStr)) {
                System.out.println("Oops!");
                System.out.println("randomUpperStr--" + randomUpperStr);
                break;
            }
        }
        System.out.println("Test End!");
//        String s = "AAAABBBCCCCCDDDDDBS";
//        minLengthByArr(s);
    }
}
